package previous.Test_0328;

import java.util.*;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //最长斐波那契子序列的长度
    public int lenLongestFibSubseq(int[] a) {
        //将数组与下标绑定
        Map<Integer, Integer> hashMap=new HashMap<Integer, Integer>();
        int n=a.length;
        for(int i=0;i<n;i++) {
            hashMap.put(a[i], i);
        }
        int[][] dp=new int[n][n];
        //初始化
        for(int i=0;i<n;i++) {
            for(int j=0;j<i;j++) {
                dp[i][j]=2;
            }
        }
        int ret=2;
        for(int i=2;i<n;i++) {
            for(int j=1;j<i;j++) {
                int x=a[i]-a[j];
                if(x<a[j]&&hashMap.containsKey(x)) {
                    dp[i][j]=dp[j][hashMap.get(a)]+1;
                }
                ret=Math.max(ret, dp[i][j]);
            }
        }
        return ret<3?0:ret;
    }
    //等差数列划分2-子序列
    public int numberOfArithmeticSlices(int[] nums) {
        Map<Long, List<Integer>> hashMap=new HashMap<Long, List<Integer>>();
        int len=nums.length;
        for(int i=0;i<len;i++) {
            long tmp=(long)nums[i];
            if(!hashMap.containsKey(tmp)) {
                hashMap.put(tmp, new ArrayList<Integer>());
            }
            hashMap.get(tmp).add(i);
        }
        int[][] dp=new int[len][len];
        int sum=0;
        for(int i=2;i<len;i++) {
            for(int j=1;j<i;j++) {
                long x=2L*nums[j]-nums[i];
                if(hashMap.containsKey(x)) {
                    for(int k:hashMap.get(x)) {
                        if(k<j) dp[j][i]+=dp[k][j]+1;
                        else break;
                    }
                }
                sum+=dp[j][i];
            }
        }
        return sum;
    }
    //回文子串
    public int countSubstrings(String s) {
        int n=s.length();
        boolean[][] dp=new boolean[n][n];
        int ret=0;
        for(int i=n-1;i<n;i--) {
            for(int j=i;j<n;j++) {
                if(s.charAt(i)==s.charAt(j)) {
                    dp[i][j]=i+1<j?dp[i+1][j-1]:true;
                }
                if(dp[i][j]) ret++;
            }
        }
        return ret;
    }
}
